% !Mode:: "TeX:UTF-8"
% Translator: Tianfan Fu
\chapter{\glsentrytext{monte_carlo}方法}
\label{chap:monte_carlo_methods}
% 581

随机算法可以粗略的分为两类：\ENNAME{Las Vegas}算法和\gls{monte_carlo}算法。
\ENNAME{Las Vegas}算法通常精确地返回一个正确答案 （或者发布一个失败报告）。
这类方法通常需要占用随机量的计算资源（通常指的是内存和运行时间）。
与此相对的，\gls{monte_carlo}方法返回一个伴随着随机量错误的答案。
花费更多的计算资源（通常包括内存和运行时间）可以减少这种随机量的错误。
在任意固定的计算资源下， \gls{monte_carlo}算法可以得到一个近似解。

对于\gls{ML}中的许多问题来说，我们很难得到精确的答案。
这类问题很难用精确的确定性的算法如\ENNAME{Las Vegas}算法解决。% 和 -> 如
取而代之的是确定性的近似算法或\gls{monte_carlo}近似方法。
这两种方法在\gls{ML}中都非常普遍。
本章主要关注\gls{monte_carlo}方法。
% 581

\section{采样和\glsentrytext{monte_carlo}方法}
\label{sec:sampling_and_monte_carlo_methods}

\gls{ML}中的许多重要工具是基于从某种分布中采样以及用这些样本对目标量做一个\gls{monte_carlo}估计。

\subsection{为什么需要采样？}
\label{sec:why_sampling}

我们希望从某个分布中采样存在许多理由。
当我们需要以较小的代价近似许多项的和或某个积分时采样是一种很灵活的选择。
有时候，我们使用它加速一些很费时却易于处理的和的估计，就像我们使用\gls{minibatch}对整个训练代价进行\gls{subsample}一样。
在其他情况下，我们需要近似一个难以处理的和或积分，例如估计一个\gls{undirected_model}中\gls{partition_function}对数的梯度时。
在许多其他情况下，抽样实际上是我们的目标，就像我们想训练一个可以从训练分布采样的模型。
% 582 

\subsection{\glsentrytext{monte_carlo}采样的基础}
\label{sec:basics_of_monte_carlo_sampling}

当无法精确计算和或积分（例如，和具有指数数量个项，且无法被精确简化）时，通常可以使用\gls{monte_carlo}采样来近似它。
这种想法把和或者积分视作某分布下的期望，然后\emph{通过估计对应的平均值来近似这个期望}。
令
\begin{align}
s = \sum_{\Vx} p(\Vx)f(\Vx) = E_p[f(\RVx)]
\end{align}
或者
\begin{align}
\label{eqn:integra}
s = \int p(\Vx)f(\Vx)d\Vx = E_p[f(\RVx)]
\end{align}
为我们所需要估计的和或者积分，写成期望的形式，$p$是一个关于随机变量$\RVx$的概率分布（求和时）或者\gls{PDF}（求积分时）。
% 582 

我们可以通过从$p$中采集$n$个样本$\Vx^{(1)},\ldots,\Vx^{(n)}$来近似$s$并得到一个经验平均值
\begin{align}	
\hat{s}_n = \frac{1}{n}\sum_{i=1}^{n}f(\Vx^{(i)}).
\end{align}
这种近似可以被证明拥有如下几个性质。
首先很容易观察到$\hat{s}$这个估计是无偏的，由于
\begin{align}
\SetE[\hat{s}_n] = \frac{1}{n}\sum_{i=1}^{n}\SetE[f(\Vx^{(i)})] = \frac{1}{n}\sum_{i=1}^{n}s = s.
\end{align}
% 582

此外，根据\firstgls{law_of_large_numbers}，如果样本$\Vx^{(i)}$独立且服从同一分布，那么其平均值几乎必然收敛到期望值，即
\begin{align}
\lim_{n\xrightarrow{}\infty} \hat{s}_n = s,
\end{align}
只需要满足各个单项的方差，即$\text{Var}[f(\Vx^{(i)})]$有界。
详细地说，我们考虑当$n$增大时$\hat{s}_n$的方差。
只要满足$\text{Var}[f(\RVx^{(i)})]<\infty$，方差$\text{Var}[\hat{s}_n]$就会减小并收敛到$0$：
\begin{align}
\text{Var}[\hat{s}_n] & = \frac{1}{n^2}\sum_{i=1}^{n}\text{Var}[f(\RVx)]\\
&  = \frac{\text{Var}[f(\RVx)]}{n}.
\end{align}
这个简单有用的结果启迪我们如何估计\gls{monte_carlo}均值中的不确定性或者等价地说是\gls{monte_carlo}估计的期望误差。
我们计算了$f(\Vx^{(i)})$的经验均值和方差\footnote{计算无偏估计的方差时，更倾向于用计算偏差平方和除以$n-1$而非$n$。}，
然后将估计的方差除以样本数$n$来得到$\text{Var}[\hat{s}_n]$的估计。
\firstgls{central_limit_theorem}告诉我们$\hat{s}_n$的分布收敛到以$s$为均值以$\frac{\text{Var}[f(\RVx)]}{n}$为方差的\gls{normal_distribution}。
这使得我们可以利用\gls{normal_distribution}的累积密度函数来估计$\hat{s}_n$的置信区间。
% 583

以上的所有结论都依赖于我们可以从基准分布$p(\RVx)$中轻易的采样，但是这个假设并不是一直成立的。
当我们无法从$p$中采样时，一个备选方案是用\gls{importance_sampling}，在\secref{sec:importance_sampling_chap17}会讲到。
一种更加通用的方式是使用一个趋近于目标分布估计的序列。
这就是\gls{mcmc}方法（见\secref{sec:markov_chain_monte_carlo_methods}）。
% 583

\section{\glsentrytext{importance_sampling}}
\label{sec:importance_sampling_chap17}

如方程~\eqref{eqn:integra}所示，在\gls{monte_carlo}方法中，对积分（或者和）分解，即确定积分中哪一部分作为概率分布$p(\Vx)$以及哪一部分作为被积的函数$f(\Vx)$（我们感兴趣的是估计$f(\Vx)$在概率分布$p(\Vx)$下的期望）是很关键的一步。
$p(\Vx)f(\Vx)$存在不唯一的分解因为它通常可以被写成
\begin{align}
\label{eqn:decomposition}
p(\Vx)f(\Vx) = q(\Vx) \frac{p(\Vx)f(\Vx)}{q(\Vx)},
\end{align}
在这里，我们从$q$分布中采样，然后估计$\frac{pf}{q}$在此分布下的均值。
许多情况中，给定$p$和$f$的情况下我们希望计算某个期望，这个问题既然是求期望，那么很自然地$p$和$f$是一种分解选择。
然而，从衡量一定采样数所达到精度的角度说，原始定义的问题通常不是最优的选择。
幸运的是，最优的选择$q^*$通常可以简单推出。
这种最优的采样函数$q^*$对应的是所谓的最优\gls{importance_sampling}。
% 584


从\eqnref{eqn:decomposition}所示的关系中可以发现，任意\gls{monte_carlo}估计
\begin{align}
\hat{s}_p = \frac{1}{n}\sum_{i=1,\Vx^{(i)}\sim p}^{n}f(\Vx^{(i)})
\end{align}
可以被转化为一个\gls{importance_sampling}的估计
\begin{align}
\hat{s}_q = \frac{1}{n}\sum_{i=1,\Vx^{(i)}\sim q}^{n}\frac{p(\Vx^{(i)})f(\Vx^{(i)})}{q(\Vx^{(i)})}.
\end{align}
我们可以容易地发现估计值的期望与$q$分布无关：
\begin{align}
\SetE_q [\hat{s}_q] = \SetE_p [\hat{s}_p] = s.
\end{align}
然而，\gls{importance_sampling}的方差却对不同$q$的选取非常敏感。
这个方差可以表示为
\begin{align}
\label{eqn:variance_of_is}
\Var [\hat{s}_q] = \Var [\frac{p(\RVx)f(\RVx)}{q(\RVx)}]/n.
\end{align}
当$q$取到
\begin{align}
q^*(\Vx) = \frac{p(\Vx)\vert f(\Vx)\vert}{Z}
\end{align}
时，方差达到最小值。
% 584


在这里$Z$表示归一化常数，选择适当的$Z$使得$q^*(\Vx)$之和或者积分为$1$。
一个好的\gls{importance_sampling}分布会把更多的权重放在被积函数较大的地方。
事实上，当$f(\Vx)$的正负符号不变时，$\Var[\hat{s}_{q^*}]=0$， 这意味着当使用最优的$q$分布时，\emph{只需要采一个样本就足够了}。
当然，这仅仅是因为计算$q^*$的时候已经解决了所有的问题。
所以这种只需要采一个样本的方法往往是实践中无法实现的。
% 584

对于\gls{importance_sampling}来说任意$q$分布都是可行的（从得到一个期望上正确的值的角度来说），$q^*$指的是最优的$q$分布（从得到最小方差的角度上考虑）。
从$q^*$中采样往往是不可行的，但是其他仍然能降低方差的$q$的选择还是可行的。
% 584  end



另一种方法是采用\firstgls{biased_importance_sampling}，这种方法有一个优势，即不需要归一化的$p$或$q$分布。
在处理离散变量的时候，\gls{biased_importance_sampling}估计可以表示为
\begin{align}
\label{eqn:bis}
\hat{s}_{\text{BIS}} & = \frac{\sum_{i=1}^{n} \frac{p(\Vx^{(i)})}{q(\Vx^{(i)})} f(\Vx^{(i)})}{\sum_{i=1}^{n}\frac{p(\Vx^{(i)})}{q(\Vx^{(i)})}} \\
& = \frac{\sum_{i=1}^{n} \frac{p(\Vx^{(i)})}{\tilde{q}(\Vx^{(i)})} f(\Vx^{(i)})}{\sum_{i=1}^{n}\frac{p(\Vx^{(i)})}{\tilde{q}(\Vx^{(i)})}} \\
& = \frac{\sum_{i=1}^{n} \frac{\tilde{p}(\Vx^{(i)})}{\tilde{q}(\Vx^{(i)})} f(\Vx^{(i)})}{\sum_{i=1}^{n}\frac{\tilde{p}(\Vx^{(i)})}{\tilde{q}(\Vx^{(i)})}},
\end{align}
其中$\tilde{p}$和$\tilde{q}$分别是分布${p}$和${q}$的未经归一化的形式，$\Vx^{(i)}$是从分布${q}$中采集的样本。
这种估计是有偏的因为$\SetE[\hat{s}_{\text{BIS}}]\neq s$，除非当$n$渐进性地趋近于$\infty$时，方程~\eqref{eqn:bis}的分母会收敛到$1$。
所以这种估计也被叫做渐进性无偏的。
% 585

尽管一个好的$q$分布的选择可以显著地提高\gls{monte_carlo}估计的效率，反之一个糟糕的$q$分布选择则会使效率更糟糕。
我们回过头来看看方程~\eqref{eqn:variance_of_is}会发现，如果存在一个$q$使得$\frac{p(\Vx)f(\Vx)}{q(\Vx)}$很大，那么这个估计的方差也会很大。
当$q(\Vx)$很小，而$f(\Vx)$和$p(\Vx)$都较大并且无法抵消$q$时，这种情况会非常明显。
$q$分布经常会取一些简单常用的分布使得我们能够从$q$分布中容易地采样。
当$\Vx$是高维数据的时候，$q$分布的简单性使得它很难于$p$或者$p\vert f\vert$相匹配。
当$q(\Vx^{(i)})\gg p(\Vx^{(i)}) \vert f(\Vx^{(i)})\vert $的时候，\gls{importance_sampling}采到了很多无用的样本（权值之和很小或趋于零）。
另一方面，当$q(\Vx^{(i)})\ll p(\Vx^{(i)}) \vert f(\Vx^{(i)})\vert $的时候， 样本会很少被采到，其对应的权值却会非常大。
正因为后一个事件是很少发生的，这些样本很难被采到，通常使得对$s$的估计出现了典型的\gls{underestimation}，很难被整体的\gls{overestimation}抵消。
这样的不均匀情况在高维数据屡见不鲜，因为在高维度分布中联合分布的动态域通常非常大。
% 585

尽管存在上述的风险，但是\gls{importance_sampling}及其变种在\gls{ML}的应用中仍然扮演着重要的角色，包括\gls{DL}算法。
比方说，\gls{importance_sampling}被应用于加速训练具有大规模词汇的神经网络\gls{language_model}的过程中（见\secref{sec:importance_sampling_chap12}）或者其他有着大量输出结点的\gls{NN}中。
此外，还可以看到\gls{importance_sampling}应用于估计\gls{partition_function}（一个概率分布的归一化常数）的过程中（详见\secref{sec:estimating_the_partition_function}）以及在深度有向图模型比如\gls{VAE}中估计似然函数的对数（详见\secref{sec:variational_autoencoders}）。
采用\gls{SGD}训练模型参数的时候\gls{importance_sampling}可以用来改进对\gls{cost_function}梯度的估计，尤其是针对于分类器模型的训练中一小部分错误分类样本产生的\gls{cost_function}。
在这种情况下更加频繁地采集这些困难的样本可以降低梯度估计的方差\citep{Hinton06}。
% 586 


\section{\glsentrytext{mcmc}方法}
\label{sec:markov_chain_monte_carlo_methods}

在许多实例中，我们希望采用\gls{monte_carlo}方法，然而往往又不存在一种直接从目标分布$p_{\text{model}}(\RVx)$中精确采样或者一个好的（方差较小的）\gls{importance_sampling}分布$q(\Vx)$。
在深度学习中，分布$p_{\text{model}}(\RVx)$往往表达成一个无向模型。
在这种情况下，为了从分布$p_{\text{model}}(\RVx)$中近似采样，我们引入了一种叫做\firstgls{markov_chain}的数学工具。
利用\gls{markov_chain}来进行\gls{monte_carlo}估计的这一类算法被称为\firstall{mcmc}算法。
\gls{mcmc}算法在\gls{ML}中的应用在\citet{koller-book2009}中花了大量篇幅描述。
\glssymbol{mcmc}算法最标准，最一般的要求是只适用模型分布处处不为$0$的情况。
因此，最方便的目标分布的表达是从\firstgls{energy_based_model}即$p(\Vx)\propto \exp(-E(\Vx))$中采样，见\secref{sec:energy_based_models}。
在\glssymbol{energy_based_model}中每一个状态所对应的概率都不为零。
事实上\glssymbol{mcmc}方法可以被广泛地应用在了许多包含概率为$0$的状态的概率分布中。
然而，在这种情况下，关于\glssymbol{mcmc}方法性能的理论保证只能依据具体不同类型的分布具体分析证明。
在\gls{DL}中，应用于所有\gls{energy_based_model}的通用理论保证是很常见的。
% 586 end


为了解释从\gls{energy_based_model}中采样的困难性，我们考虑一个包含两个变量的\glssymbol{energy_based_model}的例子，记作$p(\RSa,\RSb)$。
为了采$\RSa$，我们必须先从$p(\RSa\mid \RSb)$中采样，为了采$\RSb$，我们又必须从$p(\RSb\mid \RSa)$中采样。
这似乎成了难以解释的先有鸡还是先有蛋的问题。
\gls{directed_model}避免了这一问题因为它的图是有向无环的。
为了完成\firstgls{ancestral_sampling}，我们根据拓扑顺序采样每一个变量，给定每个变量的所有父结点的条件下，这个变量是确定能够被采样的（详见\secref{sec:sampling_from_graphical_models}）。
\gls{ancestral_sampling}定义了一种高效的，单路径的方法来采集一个样本。
% 587 begin


在一个\glssymbol{energy_based_model}中，我们通过使用\gls{markov_chain}来采样，从而避免了先有鸡还是先有蛋的问题。
\gls{markov_chain}的核心思想是以一个任意状态的点$\Vx$作为起始点。
随着时间的推移，我们随机地反复地更新状态$\Vx$。
最终$\Vx$成为了一个从$p(\Vx)$中抽出的（非常接近）比较公正的样本。
在正式的定义中，\gls{markov_chain}由一个随机状态$x$和一个转移分布$T(\Vx'\mid \Vx)$定义而成，$T(\Vx'\mid \Vx)$是一个概率分布，说明了给定状态$\Vx$的情况下随机地转移到$\Vx'$的概率。
运行一个\gls{markov_chain}意味着根据转移分布$T(\Vx'\mid \Vx)$反复地用状态$\Vx'$来更新状态$\Vx$。
% 587


为了给出\glssymbol{mcmc}方法为何有效的一些理论解释，重定义这个问题是很有用的。
首先我们关注一些简单的情况，其中随机变量$\RVx$有可数个状态。
我们将这种状态记作正整数$x$。
不同的整数$x$的大小对应着原始问题中$\Vx$的不同状态。
% 587  


接下来我们考虑如果并行地运行无穷多个\gls{markov_chain}会发生什么。
不同\gls{markov_chain}的所有状态都会被某一个分布$q^{(t)}(x)$采到，在这里$t$表示消耗的时间数。
开始时，对每个\gls{markov_chain}，我们采用一个分布$q^{{0}}$来任意地初始化$x$。
之后，$q^{(t)}$与所有之前跑过的\gls{markov_chain}有关。
我们的目标就是$q^{(t)}(x)$收敛到$p(x)$。
% 587 

因为我们已经用正整数$x$重定义了这个问题，我们可以用一个向量$\Vv$来描述这个概率分布$q$，并且满足
\begin{align}
q(\RSx = i) = v_i.
\end{align}
% 587

然后我们考虑更新单一的\gls{markov_chain}，从状态$x$到新状态$x'$。
单一状态转移到$x'$的概率可以表示为
\begin{align}
\label{eqn:transition1}
q^{(t+1)}(x') = \sum_{x} q^{(t)}(x) T(x'\mid x).
\end{align}
% 587 end


根据状态为整数的设定，我们可以将转移算子$T$表示成一个矩阵$\MA$。
矩阵$\MA$的定义如下：
\begin{align}
\MA_{i,j} = T(\RVx' = i\mid \RVx = j).
\end{align}
使用这一定义，我们可以重新写成\eqnref{eqn:transition1}。
与之前使用$q$和$T$来理解单个状态的更新相对的是，我们现在可以使用$\Vv$和$\MA$来描述当我们更新时（并行运行的）不同个\gls{markov_chain}上整个分布是如何变化的：
\begin{align}
\Vv^{(t)} = \MA \Vv^{(t-1)}.
\end{align}
% 588   head

重复地使用\gls{markov_chain}来更新就相当于重复地乘上矩阵$\MA$。
换一句话说，我们可以认为这一过程就是关于$\MA$的指数变化：
\begin{align}
\Vv^{(t)} = \MA^{t} \Vv^{(0)}.
\end{align}
% 588

矩阵$\MA$有一种特殊的结构，因为它的每一列都代表了一个概率分布。
这样的矩阵被称作是\firstgls{stochastic_matrix}。
对于任意状态$x$到任意其他状态$x'$存在一个$t$使得转移概率不为$0$，那么Perron-Frobenius定理~\citep{perron1907theorie,frobenius1908matrizen}可以保证这个矩阵的最大特征值是实数且大小为$1$。
我们可以看到所有的特征值随着时间呈现指数变化：
\begin{align}
\Vv^{(t)} = (\MV \text{diag}(\Vlambda)\MV^{-1})^{t} \Vv^{(0)} = \MV \text{diag}(\Vlambda)^t \MV^{-1} \Vv^{(0)}.
\end{align}
% 588


这个过程导致了所有的不等于$1$的特征值都衰减到$0$。
在一些额外的较为宽松的假设下，我们可以保证矩阵$\MA$只有一个特征值为$1$。
所以这个过程收敛到\firstgls{stationary_distribution}，有时也叫做\firstgls{equilibrium_distribution}。
收敛时，我们得到
\begin{align}
\label{eqn:1723}
\Vv ' = \MA \Vv = \Vv .
\end{align}
这个条件也适用于收敛之后的每一步。
这就是特征向量方程。
作为收敛的静止点，$\Vv$一定是特征值为$1$所对应的特征向量。
这个条件保证收敛到了\gls{stationary_distribution}以后，之后的采样过程不会改变不同\gls{markov_chain}的状态分布（尽管转移算子自然而然地会改变每个单独的状态）。
% 588

如果我们正确地选择了转移算子$T$，那么最终的\gls{stationary_distribution} $q$将会等于我们所希望采样的分布$p$。
我们会简要地介绍如何选择$T$，详见\secref{sec:gibbs_sampling}。
% 588


可数状态\gls{markov_chain}的大多数性质可以被推广到连续状态的\gls{markov_chain}中。
在这种情况下，一些研究者把这种\gls{markov_chain}叫做\firstgls{harris_chain}，但是这两种情况我们都用\gls{markov_chain}来表示。
通常情况下，在一些宽松的条件下，一个带有转移算子$T$的\gls{markov_chain}都会收敛到一个固定点，这个固定点可以写成如下形式：
\begin{align}
q' (\RVx') = \SetE_{\RVx\sim q}T(\RVx'\mid \RVx).
\end{align}
这个方程的离散版本就是方程~\eqref{eqn:1723}。	
当$\RVx$离散时，这个期望对应着求和，而当$\RVx$连续时，这个期望对应的是积分。
% 589 head



无论状态是连续还是离散，所有的\gls{markov_chain}方法都包括了重复，随机地更新直到最终所有的状态开始从\gls{equilibrium_distribution}中采样。
运行\gls{markov_chain}直到它达到\gls{equilibrium_distribution}的过程通常被叫做\gls{markov_chain}的\firstgls{burn_in}过程。
在\gls{markov_chain}达到\gls{equilibrium_distribution}之后，我们可以从\gls{equilibrium_distribution}中采集一个无限多数量的样本序列。
这些样本服从同一分布，但是两个连续的样本之间存在强烈的相关性。
所以一个有限的序列无法完全表达\gls{equilibrium_distribution}。
一种解决这个问题的方法是每隔$n$个样本返回一个样本，从而使得我们对于\gls{equilibrium_distribution}的统计量的估计不会被\glssymbol{mcmc}方法的样本之间的相关性所干扰。
所以\gls{markov_chain}在计算上是非常昂贵的，主要源于达到\gls{equilibrium_distribution}前需要\gls{burn_in}的时间以及在达到\gls{equilibrium_distribution}之后从一个样本转移到另一个完全无关的样本所需要的时间。
如果我们想要得到完全独立的样本，那么我们需要同时并行的运行多个\gls{markov_chain}。
这种方法使用了额外的并行计算来消除潜在因素的干扰。
使用一条\gls{markov_chain}来生成所有样本的策略和（使用多条\gls{markov_chain}）每条\gls{markov_chain}只产生一个样本的策略是两种极端。
深度学习的研究者们通常选取的\gls{markov_chain}的数目和\ENNAME{minibatch}中的样本数相近，然后从这些固定的\gls{markov_chain}集合中采集所需要的样本。
\gls{markov_chain}的数目通常选为$100$。
% 589

另一个难点是我们无法预先知道\gls{markov_chain}需要运行多少步才能到达\gls{equilibrium_distribution}。 
这段时间通常被称为\firstgls{mixing_time}。
检测一个\gls{markov_chain}是否达到平衡是很困难的。
我们并没有足够完善的理论来解决这个问题。
理论只能保证\gls{markov_chain}会最终收敛，但是无法保证其他。
如果我们从矩阵$\MA$作用在概率向量$\Vv$上的角度来分析\gls{markov_chain}，那么我们可以发现当$\MA^t$除了单个$1$以外的特征值都趋于$0$时，\gls{markov_chain}混合成功（收敛到了\gls{equilibrium_distribution}）。
这也意味着矩阵$\MA$的第二大特征值决定了\gls{markov_chain}的\gls{mixing_time}。
然而，在实践中，我们通常不能将\gls{markov_chain}表示成为矩阵的形式。
我们的概率模型所能够达到的状态是变量数的指数级别，所以表达$\Vv$、$\MA$或者$\MA$的特征值是不现实的。
由于这些阻碍，我们通常无法知道\gls{markov_chain}是否已经混合成功。
作为替代，我们只能运行一定量时间\gls{markov_chain}直到我们粗略估计这段时间是足够的，然后使用启发式的方法来决定\gls{markov_chain}是否混合成功。
这些启发性的算法包括了手动检查样本或者衡量连续样本之间的相关性。
% 590 head



\section{\glsentrytext{gibbs_sampling}}
\label{sec:gibbs_sampling}

截至目前我们已经了解了如何通过反复地更新$\Vx \xleftarrow{} \Vx'\sim T(\Vx'\mid\Vx)$从一个分布$q(\Vx)$中采样。
然而我们还没有提到过如何确定一个有效的$q(\Vx)$分布。
本书中描述了两种基本的方法。
第一种方法是从已经学习到的分布$p_{\text{model}}$中推导出$T$，下文描述了如何从\gls{energy_based_model}中采样。
第二种方法是直接用参数描述$T$，然后学习这些参数，其\gls{stationary_distribution}隐式地定义了我们所感兴趣的模型$p_{\text{model}}$。
我们将在\secref{sec:generative_stochastic_networks}和\secref{sec:other_generation_schemes}中讨论第二种方法的例子。
% 590


在\gls{DL}中，我们通常使用\gls{markov_chain}从定义为\gls{energy_based_model}的分布$p_{\text{model}}(\Vx)$中采样。
在这种情况下，我们希望\gls{markov_chain}的$q(\Vx)$分布就是$p_{\text{model}}(\Vx)$。
为了得到所期望的$q(\Vx)$分布，我们必须选取合适的$T(\Vx'\mid \Vx)$。
% 590


\firstgls{gibbs_sampling}是一种概念简单而又有效的方法。
它构造一个从$p_{\text{model}}(\Vx)$中采样的\gls{markov_chain}，其中在\gls{energy_based_model}中从$T(\RVx'\mid \RVx)$采样是通过选择一个变量$\RSx_i$，然后从$p_{\text{model}}$中该点关于在无向图$\CalG$（定义了\gls{energy_based_model}结构）中邻接点的条件分布中抽样。
给定他们所有的邻居结点只要一些变量是条件独立的，那么这些变量可以被同时采样。
正如在\secref{sec:example_the_restricted_boltzmann_machine}中看到的\glssymbol{RBM}的例子一样，\glssymbol{RBM}所有的\gls{hidden_unit}可以被同时采样，因为在给定可见单元的条件下他们相互条件独立。
同样的，所有的可见单元也可以被同时采样因为在给定\gls{hidden_unit}的情况下他们相互条件独立。
像这样的同时更新许多变量的\gls{gibbs_sampling}通常被叫做\firstgls{block_gibbs_sampling}。
% 590

设计从$p_{\text{model}}$中采样的\gls{markov_chain}还存在另外的备选方法。
比如说，Metropolis-Hastings算法在其他情景下被广泛使用。
在\gls{DL}的\gls{undirected_model}中，除了\gls{gibbs_sampling}很少使用其他的方法。
改进采样技巧也是一个潜在的研究热点。
% 590


\section{不同的\glsentrytext{mode}之间的\glsentrytext{mixing}挑战}
\label{sec:the_challenge_of_mixing_between_separated_modes}
% 591  head 

使用\glssymbol{mcmc}方法的主要难点在于他们经常\gls{mixing}得很糟糕。
理想情况下，从设计好的\gls{markov_chain}中采出的连续样本之间是完全独立的，而且在$\Vx$空间中，\gls{markov_chain}以正比于不同区域对应概率的概率访问这些区域。
然而，\glssymbol{mcmc}方法采出的样本可能会具有很强的相关性，尤其是在高维的情况下。
我们把这种现象称为慢\gls{mixing}甚至\gls{mixing}失败。
具有缓慢\gls{mixing}的\glssymbol{mcmc}方法可以被视为对\gls{energy_function}无意地执行类似于带噪声的\gls{GD}的操作，或者说等价于相对于链的状态（随机变量被采样）依据概率进行等效的噪声爬坡。
（在\gls{markov_chain}的状态空间中）从$\Vx^{(t-1)}$到$\Vx^{(t)}$该链倾向于选取很小的步长，其中能量$E(\Vx^{(t)})$通常低于或者近似等于能量$E(\Vx^{(t-1)})$，
倾向于向较低能量的区域移动。
当从可能性较小的状态（比来自$p(\Vx)$的典型样本拥有更高的能量）开始时，链趋向于逐渐减少状态的能量，并且仅仅偶尔移动到另一个\gls{mode}。
一旦该链已经找到低能量的区域（例如，如果变量是图像中的像素，则低能量的区域可以是同一对象所对应图像的一个相连的\gls{manifold}），我们称之为\gls{mode}，链将倾向于围绕着这个\gls{mode}游走（以某一种形式的随机游走）。
它时不时会走出该\gls{mode}，但是结果通常会返回该\gls{mode}或者（如果找到一条离开的路线）移向另一个\gls{mode}。
问题是对于很多有趣的分布来说成功的离开路线很少，所以\gls{markov_chain}将在一个\gls{mode}附近抽取远超过需求的样本。
% 591 


当考虑到\gls{gibbs_sampling}算法（见\secref{sec:gibbs_sampling}）时，这种现象格外明显。
在这种情况下，我们考虑在一定步数内从一个\gls{mode}移动到一个临近\gls{mode}的概率。
决定这个概率的是两个\gls{mode}之间的``能量障碍''的形状。
隔着一个巨大``能量障碍'' （低概率的区域）的两个\gls{mode}之间的转移概率是（随着能量障碍的高度）指数下降的，如在\figref{fig:chap17_good_bad_really_bad_mixing_color}中展示的一样。
当目标分布有很多\gls{mode}并且以很高的概率被低概率区域所分割，尤其当\gls{gibbs_sampling}的每一步都只是更新变量的一小部分而这一小部分变量又严重依赖其他的变量时，这会导致严重的问题。
% 591


% 592 head 
\begin{figure}[!htb]
\ifOpenSource
\centerline{\includegraphics{figure.pdf}}
\else
	\centerline{\includegraphics{Chapter17/figures/good_bad_really_bad_mixing_color}}
\fi
\caption{对于三种分布使用\gls{gibbs_sampling}所产生的路径，所有的分布\gls{markov_chain}初始值都设为\gls{mode}。
（左）一个带有两个独立变量的\gls{multivariate_normal_distribution}。
由于变量之间是相互独立的，\gls{gibbs_sampling}\gls{mixing}得很好。
（中）变量之间存在高度相关性的一个\gls{multivariate_normal_distribution}。
变量之间的相关性使得\gls{markov_chain}很难\gls{mixing}。
因为每一个变量的更新需要相对其他变量求条件分布，相关性减慢了\gls{markov_chain}远离初始点的速度。
（右）\gls{mode}之间间距很大且不在轴上对齐的混合高斯分布。
\gls{gibbs_sampling}\gls{mixing}得很慢，因为每次更新仅仅一个变量很难跨越不同的\gls{mode}。}
\label{fig:chap17_good_bad_really_bad_mixing_color}
\end{figure}


%  592
举一个简单的例子，考虑两个变量$\RSa$， $\RSb$的\gls{energy_based_model}，这两个变量都是二元的，取值$+1$或者$-1$。
如果对某个较大的正数$w$， $E(\RSa,\RSb) = - w \RSa \RSb$，那么这个模型传达了一个强烈的信息，$\RSa$和$\RSb$有相同的符号。
当$\RSa=1$时用\gls{gibbs_sampling}更新$\RSb$。
给定$\RSb$时的条件分布满足$p(\RSb=1\mid \RSa=1) = \sigma(w)$。
如果$w$的值很大，\gls{sigmoid}函数趋近于饱和，那么$b$取到$1$的概率趋近于$1$。
相同的道理，如果$\RSa=-1$，那么$\RSb$取到$-1$的概率也趋于$1$。
根据模型$p_{\text{model}}(\RSa,\RSb)$，两个变量取一样的符号的概率几乎相等。
根据$p_{\text{model}}(\RSa\mid \RSb)$，两个变量应该有相同的符号。
这也意味着\gls{gibbs_sampling}很难会改变这些变量的符号。
% 592

在实际问题中，这种挑战更加地艰巨因为在实际问题中我们不能仅仅关注在两个\gls{mode}之间的转移而是需要关注在多个\gls{mode}之间地转移。
如果由于\gls{mode}之间\gls{mixing}困难导致几个这样的转移是很艰难的，那么得到一些可靠的覆盖大部分\gls{mode}的样本集合的代价是很昂贵的，同时\gls{markov_chain}收敛到它的\gls{stationary_distribution}的过程也会非常缓慢。
% 592

通过寻找一些高度依赖变量的组以及分块同时更新块（组）中的变量，这个问题有时候可以被解决的。
然而不幸的是，当依赖关系很复杂的时候，从这些组中采样的过程从计算角度上说是难以处理的。
归根结底，\gls{markov_chain}最初就是被提出来解决这个问题，即从大量变量中采样的问题。
% 592

含有\gls{latent_variable}的模型中定义了一个联合分布$p_{\text{model}}(\Vx,\Vh)$，我们经常通过交替地从$p_{\text{model}}(\Vx\mid \Vh)$和$p_{\text{model}}(\Vh\mid \Vx)$中采样来达到抽$\Vx$的目的。
从快速\gls{mixing}的角度上说，我们更希望$p_{\text{model}}(\Vh\mid \Vx)$有很大的熵。
然而，从学习一个$\Vh$的有用表示的角度上考虑，我们还是希望$\Vh$能够包含$\Vx$的足够信息从而能够较完整地重构它，这意味$\Vh$和$\Vx$有着非常高的互信息。
这两个目标是相互矛盾的。
我们经常学习到能够将$\Vx$精确地编码为$\Vh$的\gls{generative_model}，但是无法很好\gls{mixing}。
这种情况在\gls{BM}中经常出现，一个\gls{BM}学到的分布越尖锐，该分布的\gls{markov_chain}采样越难\gls{mixing}得好。
这个问题在\figref{fig:chap17_fig-dbm-bad-mixing}中有所描述。
% 593


% 593 end
\begin{figure}[!htb]
\ifOpenSource
\centerline{\includegraphics{figure.pdf}}
\else
    \centering
    \begin{tabular}{cc}
    \includegraphics[width=0.45\figwidth]{Chapter17/figures/fig-adversarial}
    \includegraphics[width=0.45\figwidth]{Chapter17/figures/fig-dbm-bad-mixing}
    \end{tabular}
\fi
\caption{深度概率模型中一个\gls{mixing}缓慢问题的例证。
每张图都是按照从左到右从上到下的顺序的。
（左）\gls{gibbs_sampling}从MNIST数据集训练成的\gls{DBM}中采出的连续样本。
这些连续的样本之间非常相似。
由于\gls{gibbs_sampling}作用于一个深度图模型，相似度更多地是基于语义而非原始视觉特征。
但是对于吉布斯链来说从分布的一个\gls{mode}转移到另一个仍然是很困难的，比如说改变数字。
（右）从\gls{generative_adversarial_networks}中抽出的连续原始样本。
因为\gls{ancestral_sampling}生成的样本之间互相独立，所以不存在\gls{mixing}问题。
{译者注：此处左右好像搞反了。}}
\label{fig:chap17_fig-dbm-bad-mixing}
\end{figure}
% 593 end


% 593 mid
当感兴趣的分布对于每个类具有单独的\gls{manifold}结构时，所有这些问题可以使\glssymbol{mcmc}方法不那么有用：分布集中在许多\gls{mode}周围，并且这些模式由大量高能量区域分割。
我们在许多分类问题中遇到的是这种类型的分布，由于\gls{mode}之间\gls{mixing}缓慢，它将使得\glssymbol{mcmc}方法非常缓慢地收敛。
% 593



\subsection{不同\gls{mode}之间通过\glsentrytext{tempering}来\glsentrytext{mixing}}
\label{sec:tempering_to_mix_between_modes}
% 594

当一个分布有一些陡峭的峰并且被低概率区域包围时，很难在分布的不同\gls{mode}之间\gls{mixing}。
一些加速\gls{mixing}的方法是基于构造一个不同的概率分布，这个概率分布的\gls{mode}没有那么高，\gls{mode}周围的低谷也没有那么低。
\gls{energy_based_model}为这个想法提供一种简单的做法。
截止目前，我们已经描述了一个\gls{energy_based_model}的概率分布的定义：
\begin{align}
\label{eqn:1725}
p(\Vx) \propto \exp(-E(\Vx)).
\end{align}
\gls{energy_based_model}可以通过添加一个额外的控制\gls{mode}尖锐程度的参数$\beta$来加强：
\begin{align}
\label{eqn:1726}
p_{\beta}(\Vx) \propto \exp(-\beta E(\Vx)).
\end{align}
$\beta$参数可以被理解为\firstgls{temperature}的倒数，在统计物理中反映了\gls{energy_based_model}的本质。
当\gls{temperature}趋近于0时，$\beta$趋近于无穷大，此时的\gls{energy_based_model}是确定性的。
当\gls{temperature}趋近于无穷大时，$\beta$趋近于零，\gls{energy_based_model}（对离散的$\Vx$）成了均匀分布。
% 594

通常情况下，在$\beta = 1$时训练一个模型。
然而，我们利用了其他\gls{temperature}，尤其是$\beta < 1$的情况。
\firstgls{tempering}作为一种通用的策略，它通过从$\beta<1$模型中采样来实现在$p_1$的不同\gls{mode}之间快速\gls{mixing}。
% 594

基于\firstgls{tempering_transition}~\citep{Neal94b}的\gls{markov_chain}初始从高\gls{temperature}的分布中采样使其在不同\gls{mode}之间\gls{mixing}，然后从单位\gls{temperature}的分布中重新开始。
这些技巧被应用在一些模型比如\glssymbol{RBM}中~\citep{Salakhutdinov-2010}。
另一种方法是利用\firstgls{parallel_tempering}~\citep{Iba-2001}。
其中\gls{markov_chain}并行地模拟许多不同\gls{temperature}的不同状态。
最高\gls{temperature}的状态\gls{mixing}较慢，相比之下最低\gls{temperature}的状态，即\gls{temperature}为$1$时，采出了精确的样本。
转移算子包括了两个\gls{temperature}之间的随机跳转，所以一个高\gls{temperature}状态分布槽中的样本有足够大的概率跳转到低\gls{temperature}分布的槽中。
这个方法也被应用到了\glssymbol{RBM}中~\citep{Desjardins+al-2010-small,Cho10IJCNN}。
尽管\gls{tempering}这种方法前景可期，现今它仍然无法让我们在采样复杂的\gls{energy_based_model}中更进一步。
一个可能的原因是在\firstgls{critical_temperatures}时\gls{temperature}转移算子必须设置的非常慢（因为\gls{temperature}需要逐渐下降）来确保\gls{tempering}的有效性。
% 594



% 595
\subsection{深度也许会有助于\glsentrytext{mixing}}
\label{sec:depth_may_help_mixing}

当我们从\gls{latent_variable}模型$p(\Vh,\Vx)$中采样的时候，我们可以发现如果$p(\Vh\mid \Vx)$将$\Vx$编码得非常好，那么从$p(\Vx \mid \Vh)$中采样的时候，并不会太大地改变$\Vx$，那么\gls{mixing}结果会很糟糕。
解决这个问题的一种方法是使得$\Vh$成为一种将$\Vx$编码为$\Vh$的深度表达，从而使得\gls{markov_chain}在$\Vh$空间中更容易\gls{mixing}。
<bad> 在许多\gls{representation_learning}算法诸如\gls{AE}和\glssymbol{RBM}中，$\Vh$的边缘分布相比于关于$\Vx$的原始数据分布，通常表现为更加均匀、更趋近于\gls{unimodal}。
值得指出的是，这些方法往往利用所有可用的表达空间并尽量减小\gls{reconstruction_error}。
因为当训练集上的不同样本之间在$\Vh$空间能够被非常容易地区分时，我们也会很容易地最小化\gls{reconstruction_error}。
\citet{Bengio-et-al-ICML2013-small}观察到这样的现象，堆叠越深的\gls{regularize}\gls{AE}或者\glssymbol{RBM}，顶端$\Vh$空间的边缘分布越趋向于均匀和发散，而且不同\gls{mode}（比如说实验中的类别）所对应区域之间的间距也会越模糊。
在高层次的空间训练\glssymbol{RBM}使得\gls{gibbs_sampling}\gls{mixing}得更快。
然而，如何利用这种观察到的现象来辅助训练深度\gls{generative_model}或者从中采样仍然有待探索。
% 595

尽管存在\gls{mixing}的难点，\gls{monte_carlo}技巧仍然是一个有用的也是最好的可用工具。
事实上，在遇到难以处理的\gls{undirected_model}中的\gls{partition_function}时，\gls{monte_carlo}方法仍然是最基础的工具，这将在下一章详细阐述。
% 595












